#include<iostream>
#include<vector>
#include<queue>
#include<climits>

using std::vector;

struct State {
  int v;
  int dist;

  State(int v_, int dist_): v(v_), dist(dist_) {}
  
  bool operator<(const State &other) const {
    return dist < other.dist;
  }
};

struct Edge {
  int dest;
  int cost;
  
  Edge() {}

  Edge(int dest_, int cost_): dest(dest_), cost(cost_) {}
};

const int INF = INT_MAX / 2;

vector<int> find_shortest_paths(int start, const vector<vector<Edge> > &adj) {
  vector<int> dist(adj.size(), INF);
  std::priority_queue<State> queue;

  dist[start] = 0;
  queue.push(State(start, 0));

  while (!queue.empty()) {
    State cur_state = queue.top();
    int cur_v = cur_state.v;
    int cur_dist = cur_state.dist;
    queue.pop();

    if (dist[cur_v] < cur_dist) {
      continue;
    }

    for (int i = 0; i < adj[cur_v].size(); ++i) {
      int next_v = adj[cur_v][i].dest;
      int next_dist = cur_dist + adj[cur_v][i].cost;
      if (dist[next_v] > next_dist) {
        dist[next_v] = next_dist;
        queue.push(State(next_v, next_dist));
      }
    }
  }
  return dist;
}

int main() {
  // number of vertices
  int n;
  // number of edges
  int e;

  std::cin >> n;
  std::cin >> e;

  // adjacency lists
  vector<vector<Edge> > adj(n);
  for (int i = 0; i < e; ++i) {
    int s, t, cost;
    std::cin >> s >> t >> cost;
    adj[s].push_back(Edge(t, cost));
  }

  int start;
  std::cin >> start;

  vector<int> dist;
  
  dist = find_shortest_paths(start, adj);
  std::cout << "Shortest paths from " << start << " to all other vertices are:" << std::endl;
  for (int i = 0; i < n; ++i) {
    std::cout << start << "->" << i << "=" << dist[i] << std::endl;
  }
  return 0;
}
